package sort;

import java.util.*;
import java.util.Queue;
import java.util.LinkedList;

/**
 * 图的广度优先遍历
 *
 */



public class GraphBFS {
    private int[][] adjacencyMatrix; // 邻接矩阵
    private int numVertices; // 顶点数量

    // 构造函数
    public GraphBFS(int numVertices) {
        this.numVertices = numVertices;
        this.adjacencyMatrix = new int[numVertices][numVertices];
    }

    // 添加边
    public void addEdge(int source, int destination) {
        adjacencyMatrix[source][destination] = 1;
        adjacencyMatrix[destination][source] = 1; // 如果是无向图，需要添加反向边
    }

    // 广度优先遍历
    public void bfs(int start) {
        boolean[] visited = new boolean[numVertices]; // 用于记录已访问的顶点
        Queue<Integer> queue = new LinkedList<>(); // 使用队列实现BFS

        // 将起始顶点加入队列并标记为已访问
        queue.add(start);
        visited[start] = true;

        while (!queue.isEmpty()) {
            // 从队列中取出一个顶点
            int vertex = queue.poll();
            System.out.print(vertex + " "); // 访问该顶点

            // 遍历所有顶点，找到当前顶点的邻接顶点
            for (int i = 0; i < numVertices; i++) {
                if (adjacencyMatrix[vertex][i] == 1 && !visited[i]) {
                    queue.add(i); // 将邻接顶点加入队列
                    visited[i] = true; // 标记邻接顶点为已访问
                }
            }
        }
    }

    public static void main(String[] args) {
        // 创建一个图，包含6个顶点
        GraphBFS graph = new GraphBFS(6);

        // 添加边
        graph.addEdge(0, 1);
        graph.addEdge(0, 2);
        graph.addEdge(1, 3);
        graph.addEdge(1, 4);
        graph.addEdge(2, 5);
        graph.addEdge(4, 5);

        System.out.println("广度优先遍历结果：");
        graph.bfs(0); // 从顶点0开始进行BFS
    }
}
